package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/26 22:14
 * 链表中的节点每k个一组翻转
 * 算法：链表
 */
public class NC50 {
    public static void main(String[] args) {
        ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
        new NC50().reverseKGroup(node, 2);
    }

    public ListNode reverseKGroup (ListNode head, int k) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        ListNode ans = new ListNode(-1);
        ans.next = head;
        cur = ans;
        while (cur != null && n >= k) {
            // 保存下一个 node
            ListNode next = cur.next;
            cur.next = reverse(next, k);
            cur = next;
            n -= k;
        }
        return ans.next;
    }
    ListNode reverse(ListNode node, int k) {
        if (node == null) return null;
        ListNode pre = null, cur = node;
        while (cur != null && k-- > 0) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // cur 是当前翻转这组的下一个节点; 经过翻转后, node 是这组的最后一个节点
        node.next = cur;
        return pre;
    }

}
